import java.util.*;

public class Sort {
    /**插入排序
     * 思想：默认0下标是有序的，从后往前找合适的位置插入。
     * 数据越有序，排序速度越快
      * 时间复杂度：O（N^2）
  * 最好时间复杂度：O（N）
     * 空间复杂度：O（1）
     * 稳定性   ：稳定的
     * @param array
     */
    public void insertSort(int[] array){
        for (int i=1; i < array.length; i++) {
            int tmp=array[i];
            int k = i-1;//和k是等于i的，当那样会数组下标异常
            for (; k >= 0 ; k--) {
                if (tmp<array[k]){//加上等于号，就变成了不稳定的
                    array[k+1]=array[k];
                }else {//我写的时候，没有加break
                    break;
                }
            }
            array[k+1]=tmp;
        }
    }

    /**希尔排序
     * 思想：分组越多，数据越少，分组越少，数据越有序（插入排序越快）
     * 时间复杂度：O（N^1.3）
     * 空间复杂度：O（1）
     * 稳定性   ：不稳定
     * @param array
     */
    public  void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            shell(array,gap);
            gap /= 2;
        }
//整体进行插入排序
        shell(array,1);
    }

    private   void shell(int[] array,int gap) {
        //将插入排序改改就行
        for (int i=gap; i < array.length; i++) {
            int tmp=array[i];
            int k = i-gap;//和k是等于i的，当那样会数组下标异常
            for (; k >= 0 ; k-=gap) {
                if (tmp<array[k]){//加上等于号，就变成了不稳定的
                    array[k+gap]=array[k];
                }else {//我写的时候，没有加break
                    break;
                }
            }
            array[k+gap]=tmp;
        }
    }
    /**选择排序
     * 思想：每次选择一个最大/最小元素，放到指定位置。
     * 时间复杂度：O（N^2）（每次都是O（N^2)真垃圾）
     * 空间复杂度：O（1）
     * 稳定性   ：不稳定
     * @param array
     */
    public  void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int min=i;
            for (int j = i; j < array.length; j++) {
                if (array[min]>array[j]){
                    min=j;
                }
            }
            int tmp=array[i];
            array[i]=array[min];
            array[min]=tmp;
        }
    }
    public static void selectSort2(int[] array) {
        int left = 0;
        int right = array.length-1;
        while (left < right) {
            int minIndex = left;//假定最小值的下标
            int maxIndex = left;//假定最大值的下标
            for (int i = left+1; i <= right; i++) {
                if(array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if(array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }
            //这里有可能把最大值换到 minIndex的位置
            //言外之意，最大值正好在left这个地方
            swap(array,minIndex,left);
            if(maxIndex == left) {
                maxIndex = minIndex;
            }
            swap(array,maxIndex,right);
            left++;
            right--;
        }
    }
    /**堆排序
     * 思想：每次选择一个最大/最小元素，放到指定位置。
     * 时间复杂度：O（NlogN）
     * 空间复杂度：O（1）
     * 稳定性   ：不稳定
     * @param array
     */
    public static void heapSort(int[] array){
        createHeap(array);
        int end=array.length-1;
        while (end>0){
           int tmp= array[0];
           array[0]=array[end];
           array[end]=tmp;
           shiftDown(array,0,end);
           end--;
        }

    }
    private static void createHeap(int[] array){
        for (int i = (array.length-1-1)/2; i >=0 ; i--) {
            shiftDown(array,i,array.length);
        }
    }
    private static void shiftDown(int[] array,int parent,int len){
        int child=2*parent+1;
        while (child < len){
            if (child+1<len && array[child] < array[child+1]){
                child++;
            }
            if (array[child] > array[parent]){
                int tmp=array[parent];
                array[parent] = array[child];
                array[child] = tmp;
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }
    }

    /**
     * 冒泡排序：
     *  时间复杂度：（不要考虑优化）O(N^2)
     *  空间复杂度：O(1)
     *  稳定性：稳定的
     * @param array
     */
    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length-1; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j+1]) {
                    swap(array,j,j+1);
                    flg = true;
                }
            }
            if(flg == false) {
                return;
            }
        }
    }

    //n-1 + n-1 + n-1 +....
    public static void bubbleSort2(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length-1; j++) {
                if(array[j] > array[j+1]) {
                    swap(array,j,j+1);
                }
            }
        }
    }
    private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    //挖坑法：为什么左边为基准，要先走右边？，因为先走左边得话，找到得元素没地方放
    //hoare法：同理
    /**
     * 快速排序：没有优化（优化，三数取中法，和插入排序）
     *  时间复杂度：（不要考虑优化）O(N^2) O(NlogN)
     *  空间复杂度：O(logN)
     *  稳定性：不稳定
     * @param array
     */
    public static void quickSort(int[] array){
        quickSortfunc(array,0,array.length-1);
    }
    private static void quickSortfunc(int[] array,int start, int end){
       if (start >= end){
           return;
       }
        if(end - start + 1 <= 14) {
            //插入排序
            insertSort2(array,start,end);
            return;
        }
        //System.out.println("start:"+start+"  end: "+end);
        //三数取中法
        int index = midThree(array, start,end);
        swap(array,index,start);

        int  partition=partition(array,start,end);
        quickSortfunc(array,start,partition-1);
        quickSortfunc(array,partition+1,end);
    }
    //快速排序，小于一定值后，进行插入排序
    private static void insertSort2(int[] array,int left,int right) {
        for (int i = left+1; i <= right; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= left ; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    //我写得三数取中法
    private static int my_midThree(int[] array,int left,int right) {
        int mid=left+(right-left)>>1;
        int[] ret={array[left],array[mid],array[right]};
        int max=ret[0],min=ret[0];
        int sum=0;
        for (int i = 0; i < ret.length; i++) {
            sum+=ret[i];
            if (max<ret[i])max=ret[i];
            if (min>ret[i])min=ret[i];
        }
        return sum-max-min;
    }

    private static int midThree(int[] array,int left,int right) {
        int mid = (left+right) / 2;
        //6  8
        if(array[left] < array[right]) {
            if(array[mid] < array[left]) {
                return left;
            }else if(array[mid] > array[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            //array[left] > array[right]
            if(array[mid] < array[right]) {
                return right;
            }else if(array[mid] > array[left]) {
                return left;
            }else {
                return mid;
            }
        }

    }

    private static  int  partition(int[] array,int left,int right) {
        int tmp=array[left];
        while (left< right){
            while (left< right&&array[right]>=tmp){
               right--;
            }
            array[left]=array[right];
            while (left< right&&array[left]<=tmp){
                left++;
            }
            array[right]=array[left];
        }
        array[left]=tmp;
        return left;
    }
    //Hoare法
    private static int partition2(int[] array,int left,int right) {
        int tmp = array[left];
        int i = left;
        while (left < right) {
            while (left< right && array[right] >= tmp) {
                right--;
            }
            while (left< right && array[left] <= tmp) {
                left++;
            }
            swap(array,left,right);
        }
        swap(array,left,i);
        return left;
    }

    //前后指针法 【了解即可】
    private static int partition3(int[] array,int left,int right) {
        int prev = left ;
        int cur = left+1;
        while (cur <= right) {
            if(array[cur] < array[left] && array[++prev] != array[cur]) {
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,left);
        return prev;
    }


    /**
     * 非递归实现快速排序
     *
     * @param array
     */
    public static void quickSort2(int[] array) {
        Deque<Integer> stack = new LinkedList<>();
        int left = 0;
        int right = array.length-1;
        int pivot = partition(array,left,right);
        if(pivot > left+1) {
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot < right-1) {
            stack.push(pivot+1);
            stack.push(right);
        }

        while (!stack.isEmpty()) {
            right= stack.pop();
            left = stack.pop();
            pivot = partition(array,left,right);
            if(pivot > left+1) {
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot < right-1) {
                stack.push(pivot+1);
                stack.push(right);
            }
        }

    }

    /**
     * 时间复杂度：N*logN
     * 空间复杂度：N
     * 稳定性：稳定的排序
     *       插入排序    冒泡排序  归并排序
     * @param array
     */
    public static void mergeSort1(int[] array) {
        mergeSortFunc(array,0,array.length-1);
    }
    private static void mergeSortFunc(int[] array,int left,int right) {
        if(left >= right) {
            return;
        }

        int mid = (left+right) / 2;
        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid+1,right);
        merge(array,left,right,mid);
    }

    private static void merge(int[] array,int start,int end,int mid) {
//        原理其实就是合并俩个有序数组
        int s1 = start;
        //int e1 = mid;
        int s2 = mid+1;
        //int e2 = end;
        int[] tmp = new int[end-start+1];
        int k = 0;//tmp数组的下标
        while (s1 <= mid && s2 <= end) {
            if(array[s1] <= array[s2]) {
                tmp[k++] = array[s1++];
            }else {
                tmp[k++] = array[s2++];
            }
        }
        while (s1 <= mid) {
            tmp[k++] = array[s1++];
        }
        while (s2 <= end) {
            tmp[k++] = array[s2++];
        }

        for (int i = 0; i < tmp.length; i++) {
            array[i+start] = tmp[i];
        }

    }
//    归并排序得非递归方式
    public static void mergeSort(int[] array) {
        int gap = 1;
        while (gap < array.length) {
            // i += gap * 2 当前gap组的时候，去排序下一组
            for (int i = 0; i < array.length; i += gap * 2) {
                int left = i;
                int mid = left+gap-1;//有可能会越界
                if(mid >= array.length) {
                    mid = array.length-1;
                }
                int right = mid+gap;//有可能会越界
                if(right>= array.length) {
                    right = array.length-1;
                }
                merge(array,left,right,mid);
            }
            //当前为2组有序  下次变成4组有序
            gap *= 2;
        }
    }
    /**
     * 计数排序
     * 时间复杂度： O(N+范围)
     * 空间复杂度：O(范围)
     * 稳定性：
     * @param array
     */
    public static void countSort(int[] array) {
        //1. 遍历数组 找到最大值 和 最小值
        int max = array[0];
        int min = array[0];
        //O(N)
        for (int i = 1; i < array.length; i++) {
            if(array[i] < min) {
                min = array[i];
            }
            if(array[i] > max) {
                max = array[i];
            }
        }
        //2. 根据范围 定义计数数组的长度
        int len = max - min + 1;
        int[] count = new int[len];
        //3.遍历数组，在计数数组当中 记录每个数字出现的次数 O(N)
        for (int i = 0; i < array.length; i++) {
            count[array[i]-min]++;
        }
        //4.遍历计数数组
        int index = 0;// array数组的新的下标 O(范围)
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                //这里要加最小值  反应真实的数据
                array[index] = i+min;
                index++;
                count[i]--;
            }
        }
    }

}


